package games.graphPath;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Graph {
	
	private ArrayList<Vertex> _vertexList;
	private Vertex _src;
	private Vertex _dst;
	private int _size;
		
	public Graph(int numOfNodes){
		
		_vertexList = new ArrayList<Vertex>(numOfNodes);
		_size = numOfNodes;
		_src = null;
		_dst = null;
		
		
		for (int i=0; i<numOfNodes; i++){
			_vertexList.add(new Vertex(i));
		}
	}
	
	public void buildEdges(int maxCost)
	{
		Random r = new Random();
		
		int cost;
		for (int i=0; i<_vertexList.size(); i++){
			for (int j=0; j<_vertexList.size(); j++){
				if (i!=j){
					int tries = 0;
					do{
						cost = r.nextInt(maxCost);
						tries++;
					}while (tries<15 && cost>0);
					if (cost>0){
						Vertex src = _vertexList.get(i);
						Vertex dst = _vertexList.get(j); 
						src.addOutEdge(dst, cost);
						dst.addInEdge(src, cost);
					}
				}
			}
		}
		
	}
	
	public void setSrcDst(int src, int dst){
		if (_src!=null || _dst!=null)
		{
			for (Vertex v:_vertexList)
				v._distFromDest=_size+1;
		}
		_src = _vertexList.get(src);
		_dst = _vertexList.get(dst);
		_dst._distFromDest = 0;
		setDistFromDstBFS(_dst.getInNeighbors(),1);		
	}
	
	public Vertex getSrc(){
		return _src;
	}
	
	public Vertex getDst(){
		return _dst;
	}
	
	public ArrayList<Vertex> getVertexs()
	{
		return _vertexList;
	}
	
	private void setDistFromDstBFS(List<Edge> list, int dist) {
		List<Edge> toSet = new ArrayList<Edge>();
		while (!list.isEmpty())
		{
			Edge edge = list.get(0);
			if (edge.getSrc()._distFromDest>_size)
			{
				edge.getSrc()._distFromDest=dist;
				toSet.addAll(edge.getSrc().getInNeighbors());
			}
			list.remove(edge);			
		}
		if (!toSet.isEmpty()){
			setDistFromDstBFS(toSet, dist+1);
		}
	}
	
	public void printGraph()
	{
		for (int i=0; i<_vertexList.size(); i++)
		{
			System.out.print("\t" + i +"(" + _vertexList.get(i)._distFromDest + ")");
		}
		System.out.println();
				
		for (int i=0; i<_vertexList.size(); i++)
		{
			System.out.print(i);
			List <Edge> edges = _vertexList.get(i).getOutNeighbors();
			
			int curEdgeIndex = 0;
			for (int j=0; j<_vertexList.size(); j++)
			{
				if (!edges.isEmpty() && edges.size()>curEdgeIndex && edges.get(curEdgeIndex).getDst().getIndex()==j)
				{
					System.out.print("\t"+edges.get(curEdgeIndex).getCost());
					curEdgeIndex++;
				}
				else
				{
					System.out.print("\t");
				}
			}
			System.out.println();
		}
	}
	
	
	public class Vertex{
		
		private int _index;
		private ArrayList<Edge> _outEdges;
		private ArrayList<Edge> _inEdges;
		private int _distFromDest;
		
		public Vertex(int index){
			_index = index;
			_outEdges = new ArrayList<Edge>();
			_inEdges = new ArrayList<Edge>();
			_distFromDest = _size+1;
		}
		
		public void addOutEdge(Vertex neighbor, int cost){
			_outEdges.add(new Edge(this, neighbor, cost));
		}
		
		public void addInEdge(Vertex neighbor, int cost){
			_inEdges.add(new Edge(neighbor, this, cost));
		}
		
		public List<Edge> getOutNeighbors(){
			return _outEdges;
		}
		
		public List<Edge> getInNeighbors(){
			return _inEdges;
		}

		public int getIndex() {
			return _index; 
		}
		public int getDist()
		{
			return _distFromDest;
		}
		
	}
	
	public class Edge implements Comparable<Edge>{
		
		Vertex _from, _to;
		int _cost;

		public Edge(Vertex from, Vertex to, int cost) {
			_from = from;
			_to = to;
			_cost = cost;			
		}
		
		public int getCost(){
			return _cost;
		}
		
		public Vertex getSrc(){
			return _from;
		}
		
		public Vertex getDst(){
			return _to;
		}

		@Override
		public int compareTo(Edge arg0) {
			return new Integer(_cost).compareTo(new Integer(arg0.getCost()));
		}
		
	}

	public void addEdge(int from, int to, int value) {
		_vertexList.get(from).addOutEdge(_vertexList.get(to), value);
		_vertexList.get(to).addInEdge(_vertexList.get(from), value);
		
	}

}
